基礎概念

• 目的就是為了讓CPU在multiprogramming執行效率提高。
• 行程執行中包含了CPU burst和I/O burst的循環，當一個在執行時，另一個就會等待，直到輪到它執行為止，如此循環下去。
• 當一個行程中的CPU burst在等待時，可以先分配給其他行程使用。

CPU Scheduler

• Short-term scheduler：從在ready queue中的行程進行選擇，並分配CPU給其中之一。
• CPU scheduling決定行程要發生什麼事：

1. 從running轉換到waiting狀態
2. 從running轉換到ready的狀態
3. 從waiting轉換到ready的狀態
4. Terminates
   =>其中(1)和(4)，是必須做完動作，不能中斷的，為nonpreemptive；而(2)和(3)是可以中斷的，為preemptive，但須注意三點：
   1-須小心是否有使用share data。
   2-是否是在kernel model下使用
   3-是否能接受interrupt

Dispather

• 將CPU的控制權交給由short-term scheduler選擇的行程。其中包含：

1. 環境轉換
2. 轉換到使用者模組
3. 轉換到適當的user program去，並重新開始program。

• Dispatch latency：時間到了，中斷正在執行的行程，並開始另外一個。

Scheduling Criteria

• CPU utilization：使CPU盡量保持忙碌狀態。
• Througput：在單位時間內完成的工作量。
• Turnaround time：一個行程從進入CPU到完成的所需時間，而時間越短越好。
• Waiting time：行程在ready queue中已經等待多少時間，時間越短越好。
• Response time：在time-sharing的環境中，從一個request進入到得到回應的所需時間，時間越短越好。

First-Come,First-Served(FCFS) Sheduling

• 先到的行程先執行。
• 很公平，但會有效率問題。易發生Convoy effect。

Shortest-Job-First(SJF) Scheduling

• 聯繫每個行程的長度，去決定下一個CPU burst。
• SJF is optimal：以最小平均等待時間給予一個行程。
• 困難的地方在於並不確定每個job確切的執行時間。
• 是最佳化的排程演算法。

決定下個CPU Burst的長度

• 只能估算長度，但須和前一個相似。
• shortest-remaining-time-first：如果後來的job時間比正在執行的完成時間還短，會先interrupt正在執行的，等後來的job執行完成，再接續完成被中斷的job。

Priority Scheduling

• 每個行程都連接到一個整數數字，數字越小代表優先權越大。
• CPU會被分配給最高優先權的行程使用。
• 會產生問題：Starvation-因為已執行時間最短的為優先，所以低優先權的行程很有可能都不會被執行，成為「飢餓」狀態。
• 解決辦法：Aging-讓等待時間久的行程提高優先權，才能有機會被執行。

Round Robin(RR)

• 無論行程有無執行完畢，時間到即中斷。
• 每個行程可以得到1/n的CPU時間，沒有一個行程會等到q(1/n)倍的時間長才執行。

Mutilevel Queue

• Ready queue被分割成單獨的佇列：

1. foreground(interactive)
2. background(Batch)

• 每個佇列擁有自己的scheduling algorithm：

1. foreground-RR
2. background-FCFS(不太在乎要立即回應)

• Scheduling須在佇列間完成。

1. Fixed queue:可能會產生「飢餓」的機會。
2. Time slice：得到一定量的CPU時間後，在安排在行程中。

Multilevel Feedback Queue

• 可以在多個佇列間移動；Aging方法可以利用此方式執行。
• 由參數所定義：

1. 佇列的數量
2. 使用方法決定何時更新行程
3. 使用方法決定何時降級行程
4. 使用方法決定當行程需要服務時，哪個佇列該進入行程。